package src.java.medium;

import java.util.HashMap;

public class LRUCache {
    int size;
    int capacity;
    TLinkedNode head, tail;
    HashMap<Integer, TLinkedNode> cache = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        head = new TLinkedNode();
        tail = new TLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(2, 1);
        cache.put(2, 2);
        System.out.println(cache.get(2)); // returns 1
        cache.put(1, 1); // evicts key 2
        cache.put(4, 1); // evicts key 2
        System.out.println(cache.get(2)); // returns -1 (not found)
    }

    public int get(int key) {
        TLinkedNode linkedNode = cache.get(key);
        if (linkedNode == null) {
            return -1;
        }
        moveNodeToHead(linkedNode);
        return linkedNode.value;
    }

    private void moveNodeToHead(TLinkedNode linkedNode) {
        removeNode(linkedNode);
        addNodeToHead(linkedNode);
    }

    public void put(int key, int value) {
        TLinkedNode tLinkedNode = cache.get(key);
        if (tLinkedNode != null) {
            tLinkedNode.value = value;
            moveNodeToHead(cache.get(key));
            return;
        }
        tLinkedNode = new TLinkedNode(key, value);
        addNodeToHead(tLinkedNode);
        cache.put(key, tLinkedNode);
        size++;
        if (size > capacity) {
            cache.remove(tail.prev.key);
            removeNode(tail.prev);
            size--;
        }
    }

    private void removeNode(TLinkedNode linkedNode) {
        linkedNode.prev.next = linkedNode.next;
        linkedNode.next.prev = linkedNode.prev;
    }

    private void addNodeToHead(TLinkedNode linkedNode) {
        head.next.prev = linkedNode;
        linkedNode.prev = head;
        linkedNode.next = head.next;
        head.next = linkedNode;
    }

}

class TLinkedNode {
    int key;
    int value;
    TLinkedNode prev;
    TLinkedNode next;

    TLinkedNode() {

    }

    TLinkedNode(int key, int value) {
        this.key = key;
        this.value = value;
    }
}
